package com.yubest;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 *
 *
 * 示例 1：[图片] img/0019.jpg
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/1 11:11
 */
public class P0019 {

    public static void main(String[] args) {
        System.out.println(new Solution19().removeNthFromEnd(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 2));

        System.out.println(new Solution19().removeNthFromEnd(new ListNode(1), 1));

        System.out.println(new Solution19().removeNthFromEnd(new ListNode(1, new ListNode(2)), 1));
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution19 {

    /**
     * 思路：双指针，第一个指针先走n步，然后从head开始再设置第二个指针，直到第一个指针走到结束位置，第一个指针指向的位置，就是倒数第n个元素，即要删除的对象
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = head;
        while (n > 0) {
            p1 = p1.next;
            n--;
        }
        ListNode pre = null;
        ListNode p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            pre = p2;
            p2 = p2.next;
        }
        if (pre == null) {
            return head.next;
        }
        pre.next = p2.next;
        return head;
    }
}
